#ifndef __SKIP_LIST__
#define __SKIP_LIST__
#include <iostream>
#include <type_traits>
#include <cstring>
//----------------------------------------------------------------------
//
// K 需要支持比较
// V 需要支持赋值
//
//----------------------------------------------------------------------

template <typename K, typename V>
class SkipList;

/*-----------------------------------------------------------------------
 * class Node
 *-----------------------------------------------------------------------*/
template <typename K, typename V>
class Node
{
    friend SkipList<K, V>;
public:
    Node(K k, V v, int level);
    ~Node();

private:
    K       key;
    V       val;
    int     level{};
    Node  **next;
};

template <typename K, typename V>
Node<K,V>::Node(K k, V v, int level)
{
    this->key = k;
    this->val = v;
    this->level = level;
    next = new Node<K,V>*[this->level + 1];
    // std::cout << "sizeof:" << sizeof(next) << " size:" << this->level + 1 << "point:" << sizeof(next[0]) << std::endl;
    memset(next, 0, sizeof(next) * (this->level + 1));
}

template <typename K, typename V>
Node<K,V>::~Node()
{
    if (next)
    {
        delete[] next;
        next = nullptr;
    }
}

/*-----------------------------------------------------------------------
 * class SkipList
 *-----------------------------------------------------------------------*/
template <typename K, typename V>
class SkipList
{
public:
    static SkipList* create_skip_list(int level);
    ~SkipList();

    bool insert(K k, V v, bool update = false);
    void traverse();
    bool find(K k, V &v);
    bool erase(K k);


private:
    SkipList(int level);
    int get_new_level();

private:
    int         max_level_{};
    int         cur_level_{};
    int         ele_count_{};
    Node<K,V>  *header_{};
};

template <typename K, typename V>
int SkipList<K,V>::get_new_level()
{
    int k = 0;
    while (rand() % 2)
    {
        k++;
    }
    return k > max_level_ ? max_level_ : k;
}

template <typename K, typename V>
SkipList<K,V>* SkipList<K,V>::create_skip_list(int level)
{
    SkipList<K,V>* l = nullptr;
    if (level < 0 || level > 128)
    {
        std::cerr << "skip list level is range of [0, 128]" << std::endl;
    }
    else
    {
        l = new SkipList(level);
        if (!l)
        {
            std::cerr << "skip list failed:new object!" << std::endl;
        }
    }
    return l;
}

template <typename K, typename V>
SkipList<K,V>::SkipList(int level):
    max_level_(level), cur_level_(0), ele_count_(0), header_(nullptr)
{
    K k{};
    V v{};
    header_ = new Node<K,V>(k, v, level);
}

template <typename K, typename V>
SkipList<K,V>::~SkipList()
{

}

// 插入的key值不可重复
template <typename K, typename V>
bool SkipList<K,V>::insert(K k, V v, bool update)
{
    bool ret = false;
    do
    {
        Node<K,V> *current = this->header_;
        Node<K,V> *reserve[max_level_ + 1] = {nullptr};
        // 1. 填充reserve. reserve:存放每一层要插入node的前一个node的地址
        for (int i = cur_level_; i >= 0; i--)
        {
            while (current->next[i] && current->next[i]->key <= k)
            {
                current = current->next[i];
            }
            reserve[i] = current;
        }
        if (current && current->key == k && current != this->header_)
        {
            if (update)
            {
                // if (std::is_pointer<V>::value) delete current->val;
                std::cout << k << ":" << current->val << "->" << v << " insert update success." << std::endl;
                current->val = v;
                ret = true;
            }
            else
            {
                std::cerr << k << ":" << v << " insert failed! key equal!!!" << std::endl;
            }
            break;
        }
        // 2. 获取新的node的level
        int new_level = get_new_level();
        Node<K,V> *node = new Node<K,V>(k, v, new_level);
        for (int i = new_level; i > cur_level_; i--)
        {
            reserve[i] = this->header_;
        }
        cur_level_ = cur_level_ > new_level ? cur_level_ : new_level;
        // 3.
        for (int i = 0; i <= new_level; i++)
        {
            node->next[i] = reserve[i]->next[i];
            reserve[i]->next[i] = node;
        }
        std::cout << "[" << new_level << "-" << k << ":" << v << "] instert success." << std::endl;
        ret = true;
    } while(0);
    return ret;
}

template <typename K, typename V>
void SkipList<K,V>::traverse()
{
    std::cout << "==================traverse===================" << std::endl;
    Node<K,V> *current = nullptr;
    for (int i = 0; i <= cur_level_; i++)
    {
        std::cout << "level(" << i << ") ";
        current = header_->next[i];
        while (current)
        {
            std::cout << current->key << "[" << current->val << "] ";
            current = current->next[i];
        }
        std::cout << std::endl;
    }
}

template <typename K, typename V>
bool SkipList<K,V>::find(K k, V &v)
{
    bool ret = false;
    Node<K,V> *current = header_;
    for (int i = cur_level_; i >= 0 ; i--)
    {
        while(!ret && current->next[i] && current->next[i]->key <= k)
        {
            if (current->next[i]->key == k)
            {
                ret = true;
            }
            current = current->next[i];
        }
        if (ret) break;
    }

    if (ret)
    {
        v = current->val;
        std::cout << "find " << k << " in [" << current->key << ":" << current->val << "] success." << std::endl;
    }
    else
    {
        std::cout << "not find " << k << std::endl;
    }
    return ret;
}

template <typename K, typename V>
bool SkipList<K,V>::erase(K k)
{
    bool ret = false;
    Node<K,V> *current = this->header_;
    Node<K,V> *reserve[max_level_ + 1] = {nullptr};

    for (int i = cur_level_; i >= 0; i--)
    {
        while (current->next[i] && current->next[i]->key < k)
        {
            current = current->next[i];
        }
        reserve[i] = current;
    }

    if (current->next[0] && current->next[0]->key == k)
    {
        // delete ele
        ret = true;
        current = current->next[0];

        for (int i = current->level; i >= 0; i--)
        {
            if (reserve[i]->next[i]->next[i])
            {
                reserve[i]->next[i] = reserve[i]->next[i]->next[i];
            }
            else
            {
                reserve[i]->next[i] = nullptr;
            }
        }
        delete current;
        current = nullptr;
        std::cout << "erase " << k << " success." << std::endl;
    }
    else
    {
        std::cout << "erase not find " << k << std::endl;
    }
    return ret;
}

#endif